1. Field of the Invention
The present invention relates to a data transform technique for transforming integer data using a lossless Hadamard transform and outputting a transform result.
2. Description of the Related Art
An image, particularly a multi-valued image, includes many pieces of information, and requires a very large memory size for storage and a lot of time for transmission. For this reason, when storing or transmitting an image, high-efficiency encoding is used to reduce the data size of the image by performing processing to remove image redundancy or changing the contents of the image to a level at which deterioration of image quality is visually imperceptible.
For example, JPEG, which is recommended by ISO and ITU-T as an international standard encoding method for still image data, computes discrete cosine transforms (DCTs) for respective blocks (8×8 pixels) of image data, thus obtaining DCT transform coefficients. JPEG compresses the image data by quantizing the DCT transform coefficients and entropy-encoding the quantized transform coefficients. As a compression technique using this DCT, H261, MPEG-1/2/4, and the like are known in addition to JPEG.
As partial processing of this DCT transforms or processing for transforming image data, a Hadamard transform is known. The Hadamard transform is an orthogonal transform that uses a transform matrix including elements of only 1 or −1, i.e., a simplest orthogonal transform implemented using only additions and subtractions.
A transform matrix H2 of a 2-point Hadamard transform is defined by:
                              H          2                =                              1                          2                                ⁡                      [                                                            1                                                  1                                                                              1                                                                      -                    1                                                                        ]                                              (        1        )            
A general N (=2n)-point Hadamard transform matrix HN can be recursively defined by a Kronecker product between an (N/2)-point Hadamard transform matrix HN/2 and the 2-point Hadamard transform matrix H2:
                                                                        H                N                            =                                                H                                      N                    /                    2                                                  ⊗                                  H                  2                                                                                                        =                                                1                                      2                                                  ⁡                                  [                                                                                                              H                                                      N                            /                            2                                                                                                                                                H                                                      N                            /                            2                                                                                                                                                                                        H                                                      N                            /                            2                                                                                                                                                -                                                      H                                                          N                              /                              2                                                                                                                                                            ]                                                                                        (        2        )            
For example, from the above definition, a 4-point Hadamard transform matrix is expressed by:
                              H          4                =                              1            2                    ⁡                      [                                                            1                                                  1                                                  1                                                  1                                                                              1                                                                      -                    1                                                                    1                                                                      -                    1                                                                                                1                                                  1                                                                      -                    1                                                                                        -                    1                                                                                                1                                                                      -                    1                                                                                        -                    1                                                                    1                                                      ]                                              (        3        )            
This transform matrix is called a natural type, and basis vectors are not arranged in sequence order. By repeating substitutions of basis vectors, the basis vectors in the second row are moved to the fourth row, and those in the original third and fourth rows are moved up by one row. Then, a transform matrix WH4 in which the order of the basis vectors is sequence order is generated:
                              WH          4                =                              1            2                    ⁡                      [                                                            1                                                  1                                                  1                                                  1                                                                              1                                                  1                                                                      -                    1                                                                                        -                    1                                                                                                1                                                                      -                    1                                                                                        -                    1                                                                    1                                                                              1                                                                      -                    1                                                                    1                                                                      -                    1                                                                        ]                                              (        4        )            
The above transform matrix is called a Walsh type or Walsh-Hadamard transform matrix. The Hadamard transform is known as a reversible orthogonal transform. Both the natural type and Walsh type allow reversible transforms, and their transform matrices are symmetric matrices.
Another symmetric matrix obtained by permuting the basis vectors of the natural type Hadamard transform matrix H4 is available in addition to the Walsh type. That symmetric matrix is a transform matrix T4 which includes diagonal components of +1 as features and is given by:
                              T          4                =                              1            2                    ⁡                      [                                                            1                                                  1                                                  1                                                  1                                                                              1                                                  1                                                                      -                    1                                                                                        -                    1                                                                                                1                                                                      -                    1                                                                    1                                                                      -                    1                                                                                                1                                                                      -                    1                                                                                        -                    1                                                                    1                                                      ]                                              (        5        )            
The present invention will explain examples using the Hadamard transforms of this type.
Generally speaking, a Hadamard transform is a lossless transform, as described above. However, this merely means a mathematically reversible transform. That is, the reversible transform is premised on the fact that no calculation errors are generated during transform and inverse transform processes, and fixed- or floating-point calculations are required as a data format for this purpose. Also, all significant digit numbers need to be held after the transforms processing.
However, in a Hadamard transform of the type used in transform encoding, and particularly in lossless transform encoding, the number of significant digits are to be reduced as much as possible after the transform processing. More specifically, since fractional part data generated by transforming integer data is considered as a digit number (information) apparently increased from the original data, this fractional part data is to be removed. However, when this fractional part data is simply rounded, reversibility is lost. For example, when four data:
123, 78, 84, 56
undergo Hadamard transform processing using the transform matrix given by equation (5), the transform results are:
170.5, 30.5, 36.5, 8.5
When these values are converted into integers by simply rounding up their fractional parts, we have:
171, 31, 37, 9
It should be noted that the transform matrix given by equation (5) is a transposed matrix. That is, transforming the integer-converted results using equation (5) again is equivalent to inverse transforming, and their inverse transform results are:
124, 78, 84, 56
Upon examining these results, first data “123” becomes “124” via the transform and inverse transform processes. That is, this means that a Hadamard transform that outputs integer-converted data cannot guarantee reversibility.
In the following description, a Hadamard transform that outputs integer-converted data will be referred to as an integer type Hadamard transform, and an integer type Hadamard transform that allows a lossless transform will be referred to as an integer type lossless-Hadamard transform or lossless-Hadamard transform.
Related arts that implement a lossless 4-point-Hadamard transform can be roughly classified into two techniques. One technique uses a Ladder Network (ladder calculations). The other technique executes round processing of a certain rule after a linear Hadamard transform. The former is disclosed in [Shinji Fukuma, Koichi Ohyama, Masahiro Iwahashi, and Noriyoshi Kambayashi, “Lossless 8-point fast discrete cosine transform using lossless Hadamard transform”, IEICE technical report, IE99-65, pp. 37-44, October 1999] (to be referred to as reference 1 hereinafter).
The latter is disclosed in Japanese Patent Laid-Open No. 2003-258645 (to be referred to as reference 2 hereinafter).
In reference 1, the lossless transform is implemented by a complicated sequence of decomposing a 4-point Hadamard transform matrix into triangular matrices, and substituting the triangular matrices by ladder calculations. FIG. 8 shows an example of the arrangement of reference 1. As shown in FIG. 8, the circuit arrangement is complicated, and it is hard to intuitively recognize the contents of calculations. For this reason, mistakes upon software or hardware implementation are hard to be found out, and the calculation processing volume is not so small.
On the other hand, a method disclosed in reference 2 as the latter technique rounds up fractional parts of an odd number of data for transform coefficients of fractional part data obtained by the linear Hadamard transforms, and truncates fractional parts of another odd number of data. This reference 2 is characterized by only the method of round processing, but it does not devise to reduce calculations of the linear Hadamard transforms and to reduce a processing volume required for the round processing.